/*

 AAAA    CCCC   OOOO   TTTTTT   SSSSS  PPPPP
 AA  AA  CC     OO  OO    TT    SS      PP  PP
 AAAAAA  CC     OO  OO    TT     SSSS   PPPPP
 AA  AA  CC     OO  OO    TT        SS  PP
 AA  AA   CCCC   OOOO     TT    SSSSS   PP

 ######################################################
 ##########    ACO algorithms for the TSP    ##########
 ######################################################

 Version: 1.0
 File:    TSP.c
 Author:  Thomas Stuetzle
 Purpose: TSP related procedures, distance computation, neighbour lists
 Check:   README and gpl.txt
 Copyright (C) 2002  Thomas Stuetzle
 */

/***************************************************************************

 Program's name: acotsp

 Ant Colony Optimization algorithms (AS, ACS, EAS, RAS, MMAS, BWAS) for the
 symmetric TSP

 Copyright (C) 2004  Thomas Stuetzle

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 email: stuetzle no@spam informatik.tu-darmstadt.de
 mail address: Universitaet Darmstadt
 Fachbereich Informatik
 Hochschulstr. 10
 D-64283 Darmstadt
 Germany

 ***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <assert.h>

#include "InOut.h"
#include "ants.h"
#include "ls.h"
#include "utilities.h"
#include "TSP.h"

//#define M_PI 3.14159265358979323846264
long int best_til_now;
Solution best_solution;
long int n; /* number of cities in the instance to be solved */
long int (*distance)(long int, long int); /* function pointer */
struct problem instance;

static double dtrunc(double x) {
	int k;

	k = (int) x;
	x = (double) k;
	return x;
}

/*
 FUNCTION: the following four functions implement different ways of
 computing distances for TSPLIB instances
 INPUT:    two node indices
 OUTPUT:   distance between the two nodes
 */

long int round_distance(long int i, long int j)
/*
 FUNCTION: compute Euclidean distances between two nodes rounded to next
 integer for TSPLIB instances
 INPUT:    two node indices
 OUTPUT:   distance between the two nodes
 COMMENTS: for the definition of how to compute this distance see TSPLIB
 */
{
	double xd = instance.nodeptr[i].x - instance.nodeptr[j].x;
	double yd = instance.nodeptr[i].y - instance.nodeptr[j].y;
	double r = sqrt(xd * xd + yd * yd) + 0.5;

	return (long int) r;
}

long int ceil_distance(long int i, long int j)
/*
 FUNCTION: compute ceiling distance between two nodes rounded to next
 integer for TSPLIB instances
 INPUT:    two node indices
 OUTPUT:   distance between the two nodes
 COMMENTS: for the definition of how to compute this distance see TSPLIB
 */
{
	double xd = instance.nodeptr[i].x - instance.nodeptr[j].x;
	double yd = instance.nodeptr[i].y - instance.nodeptr[j].y;
	double r = sqrt(xd * xd + yd * yd) + 0.000000001;

	return (long int) r;
}

long int geo_distance(long int i, long int j)
/*
 FUNCTION: compute geometric distance between two nodes rounded to next
 integer for TSPLIB instances
 INPUT:    two node indices
 OUTPUT:   distance between the two nodes
 COMMENTS: adapted from concorde code
 for the definition of how to compute this distance see TSPLIB
 */
{
	double deg, min;
	double lati, latj, longi, longj;
	double q1, q2, q3;
	long int dd;
	double x1 = instance.nodeptr[i].x, x2 = instance.nodeptr[j].x, y1 =
			instance.nodeptr[i].y, y2 = instance.nodeptr[j].y;

	deg = dtrunc(x1);
	min = x1 - deg;
	lati = M_PI * (deg + 5.0 * min / 3.0) / 180.0;
	deg = dtrunc(x2);
	min = x2 - deg;
	latj = M_PI * (deg + 5.0 * min / 3.0) / 180.0;

	deg = dtrunc(y1);
	min = y1 - deg;
	longi = M_PI * (deg + 5.0 * min / 3.0) / 180.0;
	deg = dtrunc(y2);
	min = y2 - deg;
	longj = M_PI * (deg + 5.0 * min / 3.0) / 180.0;

	q1 = cos(longi - longj);
	q2 = cos(lati - latj);
	q3 = cos(lati + latj);
	dd = (int) (6378.388 * acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3))
			+ 1.0);
	return dd;

}

long int att_distance(long int i, long int j)
/*
 FUNCTION: compute ATT distance between two nodes rounded to next
 integer for TSPLIB instances
 INPUT:    two node indices
 OUTPUT:   distance between the two nodes
 COMMENTS: for the definition of how to compute this distance see TSPLIB
 */
{
	double xd = instance.nodeptr[i].x - instance.nodeptr[j].x;
	double yd = instance.nodeptr[i].y - instance.nodeptr[j].y;
	double rij = sqrt((xd * xd + yd * yd) / 10.0);
	double tij = dtrunc(rij);
	long int dij;

	if (tij < rij)
		dij = (int) tij + 1;
	else
		dij = (int) tij;
	return dij;
}

long int ** compute_distances(void)
/*
 FUNCTION: computes the matrix of all intercity distances
 INPUT:    none
 OUTPUT:   pointer to distance matrix, has to be freed when program stops
 */
{
	long int i, j;
	long int **matrix;

	try {
		matrix = new long int * [n];
		for(i = 0;i<n;i++) {
			matrix[i] = new long int[n];
		}
	} catch(int e) {
		fprintf(stderr, "Out of memory, exit.");
		exit(1);
	}

	for (i = 0; i < n; i++) {
		matrix[i] = (long int *) (matrix + n) + i * n;
		for (j = 0; j < n; j++) {
			matrix[i][j] = distance(i, j);
		}
	}
	return matrix;
}

long int ** compute_nn_lists(void)
/*
 FUNCTION: computes nearest neighbor lists of depth nn for each city
 INPUT:    none
 OUTPUT:   pointer to the nearest neighbor lists
 */
{
	long int i, node, nn;
	long int *distance_vector;
	long int *help_vector;
	long int **m_nnear;

	TRACE ( printf("\n computing nearest neighbor lists, "); )

	nn = MAX(nn_ls,nn_ants);
	if (nn >= n)
		nn = n - 1;
	DEBUG ( assert( n > nn ); )

	TRACE ( printf("nn = %ld ... \n",nn); )

	if ((m_nnear = (long int **) malloc(sizeof(long int) * n * nn + n
			* sizeof(long int *))) == NULL) {
		exit(EXIT_FAILURE);
	}distance_vector = new long int[n];//calloc(n, sizeof(long int));
	help_vector = new long int [n];//calloc(n, sizeof(long int));

	for (node = 0; node < n; node++) { /* compute cnd-sets for all node */
		m_nnear[node] = (long int *) (m_nnear + n) + node * nn;

		for (i = 0; i < n; i++) { /* Copy distances from nodes to the others */
			distance_vector[i] = instance.distance[node][i];
			help_vector[i] = i;
		}
		distance_vector[node] = LONG_MAX; /* city is not nearest neighbour */
		sort2(distance_vector, help_vector, 0, n - 1);
		for (i = 0; i < nn; i++) {
			m_nnear[node][i] = help_vector[i];
		}
	}
	free(distance_vector);
	free(help_vector);
	TRACE ( printf("\n    .. done\n"); )
	return m_nnear;
}

long int compute_tour_length(long int *t)
/*
 FUNCTION: compute the tour length of tour t
 INPUT:    pointer to tour t
 OUTPUT:   tour length of tour t
 */
{
	int i;
	long int tour_length = 0;

	for (i = 0; i < n; i++) {
		if (i + 1 < n)
			tour_length += instance.distance[t[i]][t[i + 1]];
		else
			tour_length += instance.distance[t[i]][t[0]];
	}
	return tour_length;
}

